#include<iostream>
#include<vector>
#include<chrono>

using namespace std;

class Solution {
public:
    // 最大公共子串的长度
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        return dp(text1, text2, m-1, n-1);
    }

    //text1[0~i], text2[0~j] 的lcs 长度
    int dp(string text1, string text2, int i, int j){
        if(i == -1 || j == -1) return 0;
        if(text1[i] == text2[j]){
            // 找到一个公共字符
            return dp(text1, text2, i-1, j-1) + 1;
        }else{
            // 哪个可以让lcs 更大就选哪一个
            return max(dp(text1, text2, i-1, j), dp(text1, text2, i, j-1));
        }
        
    }

    // 带缓存
    int lcs(string text1, string text2){
        int m = text1.size();
        int n = text2.size();
        vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
        // 从小往大方向推算
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                // cout<<"i="<<i<<""<<"j="<<j<<endl;
                // 状态转移方程
                if(text1[i-1] == text2[j-1]){ // 找到一个
                    cout<<"find match="<<i-1<<","<<j-1<<": "<<text1[i-1]<<endl;
                    dp[i][j] = 1 + dp[i-1][j-1];
                }else{ // 选择能让lcs 更长的
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        print(dp);

        return dp[m][n];
    }

    void print(vector<vector<int> > twod){
        for(auto row : twod){
            for(auto column : row){
                cout<<column<<"\t";
            }
            cout<<endl;
        }
    }
};

int main(){

    // string text1 = "fcvafurqjylclorwfoladwfqzkbebslwnmpmlkbezkxoncvwhstwzwpqxqtyxozkpgtgtsjobujezgrkvevklmludgtyrmjaxyputqbyxqvupojutsjwlwluzsbmvyxifqtglwvcnkfsfglwjwrmtyxmdgjifyjwrsnenuvsdedsbqdovwzsdghclcdexmtsbexwrszihcpibwpidixmpmxshwzmjgtadmtkxqfkrsdqjcrmxkbkfoncrcvoxuvcdytajgfwrcxivixanuzerebuzklyhezevonqdsrkzetsrgfgxibqpmfuxcrinetyzkvudghgrytsvwzkjulmhanankxqfihenuhmfsfkfepibkjmzybmlkzozmluvybyzsleludsxkpinizoraxonmhwtkfkhudizepyzijafqlepcbihofepmjqtgrsxorunshgpazovuhktatmlcfklafivivefyfubunszyvarcrkpsnglkduzaxqrerkvcnmrurkhkpargvcxefovwtapedaluhclmzynebczodwropwdenqxmrutuhehadyfspcpuxyzodifqdqzgbwhodcjonypyjwbwxepcpujerkrelunstebopkncdazexsbezmhynizsvarafwfmnclerafejgnizcbsrcvcnwrolofyzulcxaxqjqzunedidulspslebifinqrchyvapkzmzwbwjgbyrqhqpolwjijmzyduzerqnadapudmrazmzadstozytonuzarizszubkzkhenaxivytmjqjgvgzwpgxefatetoncjgjsdilmvgtgpgbibexwnexstipkjylalqnupexytkradwxmlmhsnmzuxcdkfkxyfgrmfqtajatgjctenqhkvyrgvapctqtyrufcdobibizihuhsrsterozotytubefutaxcjarknynetipehoduxyjstufwvkvwvwnuletybmrczgtmxctuny";
    // string text2 = "nohgdazargvalupetizezqpklktojqtqdivcpsfgjopaxwbkvujilqbclehulatshehmjqhyfkpcfwxovajkvankjkvevgdovazmbgtqfwvejczsnmbchkdibstklkxarwjqbqxwvixavkhylqvghqpifijohudenozotejoxavkfkzcdqnoxydynavwdylwhatslyrwlejwdwrmpevmtwpahatwlaxmjmdgrebmfyngdcbmbgjcvqpcbadujkxaxujudmbejcrevuvcdobolcbstifedcvmngnqhudixgzktcdqngxmruhcxqxypwhahobudelivgvynefkjqdyvalmvudcdivmhghqrelurodwdsvuzmjixgdexonwjczghalsjopixsrwjixuzmjgxydqnipelgrivkzkxgjchibgnqbknstspujwdydszohqjsfuzstyjgnwhsrebmlwzkzijgnmnczmrehspihspyfedabotwvwxwpspypctizyhcxypqzctwlspszonsrmnyvmhsvqtkbyhmhwjmvazaviruzqxmbczaxmtqjexmdudypovkjklynktahupanujylylgrajozobsbwpwtohkfsxeverqxylwdwtojoxydepybavwhgdehafurqtcxqhuhkdwxkdojipolctcvcrsvczcxedglgrejerqdgrsvsxgjodajatsnixutihwpivihadqdotsvyrkxehodybapwlsjexixgponcxifijchejoxgxebmbclczqvkfuzgxsbshqvgfcraxytaxeviryhexmvqjybizivyjanwxmpojgxgbyhcruvqpafwjslkbohqlknkdqjixsfsdurgbsvclmrcrcnulinqvcdqhcvwdaxgvafwravunurqvizqtozuxinytafopmhchmxsxgfanetmdcjalmrolejidylkjktunqhkxchyjmpkvsfgnybsjedmzkrkhwryzan";

    // string text1 = "ylqpejqbalahwr";
    // string text2 = "yrkzavgdmdgtqpg";



    string text1 = "babcde";
    string text2 = "acze";

    Solution slu;
    auto start = std::chrono::steady_clock::now();
    // int ret = slu.longestCommonSubsequence(text1, text2);
    int ret = slu.lcs(text1, text2);
    auto end = chrono::steady_clock::now();
    chrono::duration<double> elapse_seconds = end - start;
    cout<<text1<<","<<text2<< ","<<"lcs length: "<<ret<<endl;
    cout<<"time cost:" <<elapse_seconds.count()<<endl;
    return 0;
}